package leetcode.linkedlist;

import leetcode.linkedlist.common.LinkedListUtils;
import leetcode.linkedlist.common.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution143 {
    public void reorderList(ListNode head) {
        /**
         * 方法二：
         *
         * 寻找链表中点 + 链表逆序 + 合并链表
         * 注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。
         * 这样我们的任务即可划分为三步：
         * 找到原链表的中点（参考「876. 链表的中间结点」）。
         * 我们可以使用快慢指针来 O(N)O(N) 地找到链表的中间节点。
         * 将原链表的右半端反转（参考「206. 反转链表」）。
         * 我们可以使用迭代法实现链表的反转。
         * 将原链表的两端合并。
         * 因为两链表长度相差不超过 11，因此直接合并即可。
         */
        // 本题解法使用的是线性表, 链表转线性表再处理
        LinkedListUtils.reorderList(head);
    }
}

public class leetcode143 {
    public static void main(String[] args) {
        Solution143 solution143 = new Solution143();
        int[] nums = {1, 2, 3, 4};
        test143(solution143, nums);
    }

    private static void test143(Solution143 solution143, int[] nums) {
        ListNode head = LinkedListUtils.generateLinkedListByArray(nums);
        solution143.reorderList(head);
        System.out.println(LinkedListUtils.getLinkedListVals(head));
    }
}
